In robotic competitions such as the FIRST Robotics Competition (FRC), it is often necessary for a robot to locate rectangular targets. These targets mark goals that the robot must locate in order to score a game element. For example, in the 2011-2012 FRC competition season, rectangles made of reflective tape marked the location of several basketball hoops, and robots had to score a foam basketball game element into said hoops in order to win the game.
Existing methods of target location that are commonly used in FRC robotics competitions and in the industry include blob detection and feature detection techniques such as the probabilistic Hough Transform (embodied in rectangle detection software such as the OpenCV public domain image processing library).
When evaluating the use of these existing methods for robot target detection, two criteria must be applied: (1) “Does the method accurately find the center of the target rectangle?”; and (2) “Can the method be run at a high enough frame rate (images processed per second) to allow the robot to adjust its firing mechanism in real time under game conditions on the low end computing hardware allowed in the competition?” A frame rate on the order of 15 to 20 frames per second is the absolute minimum that is effective in this kind of application.
A prior art method known as blob detection entails either looking for a specific color or areas where there are high levels of contrast. This method is fast because the actual processing is not very complicated and does not involve large numbers of steps. However, tests showed that the method does not provide a sufficiently accurate identification of the center of a target to score game elements with a high degree of certainty. Therefore, blob detection passes the frames-per-second test but fails to find the target center accurately enough to actually score points in many common situations.
The prior art also includes various kinds of feature detection algorithms to find rectangles. These are more complicated methods than blob detection, but can yield additional data and more accurate rectangle size and position information. Such methods generally involve finding line segments in an image and then attempting to form shapes from them. Using feature detection, a definite center to a shape can be identified, as opposed to only an estimate provided by blob detection. In tests undertaken in the development of the present invention, it was discovered that OpenCVs probabilistic Hough Transform, a method known in prior art, was accurate in identifying target centers, but was far too slow to provide real time feedback to the robot in order to acquire the target for scoring purposes. In addition, the Hough Transform algorithm required a very pristine image in order to operate. Real world images always contain significant noise, and to make the algorithm effective in practice would require extensive noise filtering to preprocess the image, which would make it even slower.